#ifndef  SIMPLE_KD_TREE_H
#define SIMPLE_KD_TREE_H


#include "stdafx.h"
#include <iostream>
#include "Maths.h"
#include <random>
#include <list>
#include <algorithm>

#define QUOTA 20;

using namespace std;

template <typename T>
class TestKdNode
{
private:
	

public :
	TestKdNode<T> *leftChild;
	TestKdNode<T> *rightChild;
	vector<Vec3<T>> children;
	TestKdNode<T> *parentNode;
	bool hasChildren;
	BoundingBox<T> *nodeBoundingBox;
	int splittingAxis;
	float amount;

	TestKdNode()
	{
		this->hasChildren = false;
	}

	~TestKdNode()
	{
		delete this->leftChild;
		delete this->rightChild;
		delete nodeBoundingBox;
	}

	TestKdNode(vector<Vec3<T>*> currentCoords, TestKdNode<T> *parentNode)
	{
		this->parentNode = parentNode;
		children = currentCoords;
		this->hasChildren = true;
	}

	TestKdNode(TestKdNode<T> *parentNode)
	{
		this->parentNode = parentNode;
		this->hasChildren = true;
	}


	void SetLeftChild(TestKdNode<T> *node)
	{
		this->leftChild = node;
	}

	void SetRightChild(TestKdNode<T> *node)
	{
		this->rightChild = node;
	}

	TestKdNode<T> *GetRightChild()
	{
		return this->rightChild;
	}

	TestKdNode<T> *GetLeftChild()
	{
		return this->leftChild;
	}

	bool CheckIntersection(Vec3<T> o, Vec3<T> d)
	{
		return this->nodeBoundingBox->CheckIntersection(o, d);
	}

	Vec3<T> GetBoxIntersection(Vec3<T> o, Vec3<T> d)
	{
		return this->nodeBoundingBox->GetLineBoxIntersection(o, d);
	}
};

template<typename T>
bool SortPointByXAxis(Vec3<T> xVec, Vec3<T> yVec)
{
	return xVec.x < yVec.x;
};

template<typename T>
bool SortPointByYAxis(Vec3<T> xVec, Vec3<T> yVec)
{
	return xVec.y < yVec.y;
};


template<typename T>
bool SortPointByZAxis(Vec3<T> xVec, Vec3<T> yVec)
{
	return xVec.z < yVec.z;
};


template <typename T>
class TestKdTree
{
public:
	TestKdNode<T> *rootNode;
	TestKdTree(vector<Vec3<T>> coords)
	{
		this->rootNode = new TestKdNode<T>();
		CreateKdTree(coords, this->rootNode, 0);
	}

	void CreateKdTree(vector<Vec3<T>> &coords, TestKdNode<T> *currentNode, int depth)
	{
		T xAxisLength = 0;
		T yAxisLEngth = 0;
		T zAxisLength = 0;
		//get min and max values for bounding box
		T minXAxis = INT_MAX;
		T maxXAxis = INT_MIN;
		T minYAxis = INT_MAX;
		T maxYAxis =  INT_MIN;
		T minZAxis = INT_MAX;
		T maxZAxis = INT_MIN;

		//therefore loop through all the points
		for(int index = 0; index < coords.size(); index++ )
		{
			Vec3<T> currentPoint = coords[index];

			minXAxis = min(currentPoint.x, minXAxis);
			maxXAxis = max(currentPoint.x, maxXAxis);
			minYAxis = min(currentPoint.y, minYAxis);
			maxYAxis = max(currentPoint.y, maxYAxis);
			minZAxis = min(currentPoint.z, minZAxis);
			maxZAxis = max(currentPoint.z, maxZAxis);
		}
		
		//the bounding box is an axis aligned bounding box
		currentNode->nodeBoundingBox = new BoundingBox<T>(Vec3<T>(minXAxis, minYAxis, minZAxis), Vec3<T>(maxXAxis, maxYAxis, maxZAxis));


		if(coords.size() <= 50)
		{
			currentNode->hasChildren = true;
			currentNode->children = coords;
		}
		else
		{
			xAxisLength = maxXAxis - minXAxis;
			yAxisLEngth = maxYAxis - minYAxis;
			zAxisLength = maxZAxis - minZAxis;
			
			if(xAxisLength > yAxisLEngth && xAxisLength > zAxisLength)
			{
				
				currentNode->splittingAxis = 0;
				sort(coords.begin(), coords.end(), SortPointByXAxis<T>);
			}
			else if(yAxisLEngth > xAxisLength && yAxisLEngth > zAxisLength)
			{
				
				currentNode->splittingAxis = 1;
				sort(coords.begin(), coords.end(), SortPointByYAxis<T>);
			}
			else 
			{
				
				currentNode->splittingAxis = 2;
				sort(coords.begin(), coords.end(), SortPointByZAxis<T>);
			}


			int middleVector = coords.size() % 2 == 0? coords.size()/ 2 - 1 : coords.size() / 2;
			Vec3<T> chosenNumber = coords[middleVector];
			
			if(currentNode->splittingAxis == 0)
			{
				currentNode->amount = chosenNumber.x;
			}
			else if(currentNode->splittingAxis == 1)
			{
				currentNode->amount = chosenNumber.y;
			}
			else 
			{
				currentNode->amount = chosenNumber.z;
			}

			vector<Vec3<T>> leftChildren;
			vector<Vec3<T>> rightChildren;
			
			for(int index = 0; index < coords.size(); index++)
			{
				Vec3<T> currentPoint = coords[index];
				
				if(currentNode->splittingAxis == 0)
				{
					if(currentPoint.x <= currentNode->amount)
					{
						leftChildren.push_back(currentPoint);
					}
					else
					{
						rightChildren.push_back(currentPoint);
					}
				}
				else if(currentNode->splittingAxis == 1)
				{
					if(currentPoint.y <= currentNode->amount)
					{
						leftChildren.push_back(currentPoint);
					}
					else
					{
						rightChildren.push_back(currentPoint);
					}
				}
				else
				{
					if(currentPoint.z <= currentNode->amount)
					{
						leftChildren.push_back(currentPoint);
					}
					else
					{
						rightChildren.push_back(currentPoint);
					}
				}
			}

			TestKdNode<T> *leftChild = new TestKdNode<T>(currentNode);
			TestKdNode<T> *rightChild = new TestKdNode<T>(currentNode);

			currentNode->leftChild = leftChild;
			currentNode->rightChild = rightChild;

			currentNode->hasChildren = false;

			CreateKdTree(leftChildren, leftChild, ++depth);
			CreateKdTree(rightChildren, rightChild, ++depth);
		}
	}



	bool CheckIntersection(Ray<T> *ray)
	{
		return CheckIntersection(ray, this->rootNode);
	}

	bool CheckIntersection(	Ray<T> * ray, TestKdNode<T> *currentNode)
	{
		if(currentNode->children.size() > 0)
		{
			for(int pointIndex =0; pointIndex < currentNode->children.size(); pointIndex++)
			{
				Vec3<T> currentPoint = currentNode->children[pointIndex];
				if(ray->dir == currentPoint)
				{
					return true;
				}
			}

			return false;
		}
		else
		{
			if(currentNode->CheckIntersection(ray->orig, ray->dir))
			{
				bool hitLeft = false , hitRight = false;

				hitLeft = CheckIntersection(ray, currentNode->leftChild);
				hitRight = CheckIntersection(ray, currentNode->rightChild);

				return hitLeft || hitRight;

			}
			else
			{
				return false;
			}
		
		}
	}
};

#endif // ! SIMPLE_KD_TREE_H